package sorter;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/**
 * 桶排序：将元素放入指定数目的桶中，对每个桶中的元素分别进行排序，最后进行合并。
 * 时间复杂度：创建桶O(k)，获取最大最小值O(n)，向桶中添加元素O(n)，各桶排序O(k * (n/k)log(n/k))=O(nlog(n/k))，倾倒O(n)，因此复杂度O(k+n+nlog(n/k))
 * 稳定性：可以稳定
 * @author Zhang Ziyi
 */
public class BucketSorter implements Sorter {
    @Override
    public void sort(int[] arr) {
        bucketSort(arr, 3);
    }

    private void bucketSort(int[] arr, int bucketSize) {
        // 创建桶
        ArrayList<Integer>[] bucket = initializeBucket(bucketSize);
        // 计算桶容量和最小值
        int[] boundaryAndMin = countBoundary(arr, bucketSize);
        int boundary = boundaryAndMin[0], min = boundaryAndMin[1];
        // 向桶中添加元素
        fillBucket(arr, bucket, bucketSize, min, boundary);
        // 桶中元素排序
        sortEachBucket(bucket);
        // 倾倒桶中元素到数组
        dump(arr, bucket);
    }

    private ArrayList<Integer>[] initializeBucket(int bucketSize) {
        ArrayList<Integer>[] bucket = new ArrayList[bucketSize];
        for (int i = 0; i < bucketSize; i++) {
            bucket[i] = new ArrayList<>();
        }
        return bucket;
    }

    private void dump(int[] arr, ArrayList<Integer>[] bucket) {
        int i = 0;
        for (ArrayList<Integer> list : bucket) {
            for (Integer num : list) {
                arr[i++] = num;
            }
        }
    }

    /**
     * 计算桶容量
     */
    private int[] countBoundary(int[] arr, int bucketSize) {
        int[] minAndMax = findMaxAndMin(arr);
        int min = minAndMax[0], max = minAndMax[1];
        int boundary = (max - min) / bucketSize;
        if (boundary < 1) {
            throw new IllegalArgumentException("桶数量设置不合理！");
        }
        return new int[]{(max - min) / bucketSize, min}; // i - min / boundary 就是元素桶的下标
    }

    /**
     * 对每个桶进行排序
     */
    private void sortEachBucket(ArrayList<Integer>[] bucket) {
        for (ArrayList<Integer> singleBucket : bucket) {
            Collections.sort(singleBucket);
        }
    }

    /**
     * 填充桶
     *
     * @param arr        数组
     * @param bucket     桶
     * @param bucketSize 桶大小
     * @param min        元素最小值
     */
    private void fillBucket(int[] arr, ArrayList<Integer>[] bucket, int bucketSize, int min, int boundary) {
        for (int num : arr) {
            int countedIndex = (num - min) / boundary;
            int realIndex = countedIndex == bucketSize ? bucketSize - 1 : countedIndex;
            bucket[realIndex].add(num);
        }
    }

    /**
     * 寻找数组中的最大值和最小值
     */
    private int[] findMaxAndMin(int[] arr) {
        int minIndex = 0, maxIndex = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < arr[minIndex]) {
                minIndex = i;
                continue;
            }
            if (arr[i] > arr[maxIndex]) {
                maxIndex = i;
            }
        }
        return new int[]{arr[minIndex], arr[maxIndex]};
    }
}
